Error correcting codes modify a message by adding memory and/or redundancy so that errors that occur during transmission over a channel can be detected and possibly corrected. One such error correcting code is called a product code. A representative product code is defined in the ANSI/TIA-902.BAAD standard. A product code is a multidimensional error correcting code where each dimension of the code is constructed using a constituent code. Block codes, such as Bose Chaudhuri Hocquenghem (BCH) codes, are often used as constituent codes of a product code. A product code can have a different constituent code in each dimension. Product codes are also called block product codes, block turbo codes, and block product turbo codes in the art.
Decoding product codes is a complex task and can be performed iteratively using soft-input soft-output (SISO) constituent decoders operating on constituent codewords. A soft input for the subsequent decoding phase may be computed using the soft output from the current decoding phase in a similar manner to the decoding process for turbo codes.
The soft input and soft output of each bit position in a given codeword can be, for example, a likelihood ratio or log-likelihood ratio (LLR) as is commonly used in maximum likelihood (ML) decoding and maximum a posterior (MAP) decoding. When LLRs are used, the soft input is called the input LLR, and the soft output is called the output LLR. The extrinsic LLR of a given bit position is a function of the LLRs of the other bits in the codeword, is generated from the input LLR, and is used to compute the input LLR for the next phase of the decoding iteration. In one example, the extrinsic LLR is the difference between the output LLR and input LLR.
One soft-input soft-output (SISO) decoder for constituent codes is a Chase decoder. Upon receiving a length n soft input vector for a given constituent block code, a binary vector Y and a set of test patterns Zi are formed (created) from the soft input vector in the Chase decoder. The forming of test patterns is performed by a Chase algorithm within the Chase decoder. A hard-input hard-output (HIHO) block decoder is used to decode each binary vector Xi=(Y+Zi), where the “+” for a binary vector can represent the exclusive-or operator. If the hard-input hard-output decoder is successful, the resulting codeword Ci from the hard decoding of Xi is saved in a set S. In addition to each codeword in S, an associated metric is saved, where the associated metric can be computed from the soft input, the test pattern, and the resulting codeword. In certain embodiments, a hard-input hard-output decoder can be called a hard decoder.
The soft output Chase decoder calculates the soft output for each bit j in the received codeword based on two or more codewords in S and the associated metrics. One codeword is the best estimate D, which is practically always found unless the set S is empty. The other is a competing codeword Cj that has the best metric among all codewords in S that differ from D at position j. In the Chase decoder, the competing codeword Cj is frequently not found due to the limited number of test patterns the Chase decoder examines. The soft output calculation is typically the most complex aspect of Chase decoding. Hence, there is a need to reduce the complexity of the soft output calculation. Since a competing codeword Cj may not be found for each position, there are typically many positions without a non-estimated (valid) soft output value. For applications that need soft output value for each bit position, such as decoding product codes, there is a need to estimate the soft output value for the positions without a valid soft output value. After Chase decoding, the output LLR vector comprises c unavailable output LLR values and n−c valid output LLR values. As a result, there are only n−c valid extrinsic LLR values available for subsequent decoding. In order to decode successfully, the extrinsic LLR needs to be estimated for the c unavailable output LLR values.
FIG. 1 shows a basic flowchart 100 of a Chase decoder illustrating examining the set of test patterns (block 110) to produce a set S of candidate codewords and generating the soft output vector (block 120) from the set S wherein processing the test patterns and generating the soft output are decoupled.
FIG. 2 provides an exemplary flowchart 200 depicting processing the test patterns. A binary vector Y is generated (block 205) and a set of test patterns Zi are formed from the soft input vector in the Chase decoder (block 210). The forming of test patterns is performed by a Chase algorithm within the Chase decoder. An index i is initialized to 1 (block 215), and a hard-input hard-output (HIHO) block decoder is used to decode each binary vector Xi=(Y+Zi) (block 220), where the “+” for a binary vector can represent the exclusive-or operator. If the hard-input hard-output decoder is successful (block 225), the resulting codeword Ci from the hard decoding of Xi is saved in a set S and an associated metric is also saved (block 230). The associated metric can be computed from the soft input, the test pattern, and the resulting codeword. A successful decoding is when a codeword is produced by the decoder; otherwise, there is nothing to save to the set S. An example of a decoder that has unsuccessful decodings (or decoding failures) would be a bounded distance (BD) decoder that only produces a codeword when Xi is within Hamming weight t of a codeword. The index i is then incremented (block 235) and while the index i is less than or equal to the number of test patterns (block 240), the HIHO decoding process (blocks 220-230) is performed on each test pattern.
The Chase decoder attempts to calculate the soft output for each bit j in the received codeword based on two or more codewords in S. A simplified Chase decoder can use one codeword that is the best estimate D (which is practically always found unless the set S is empty), and another (per bit j) that is the best competing codeword Cj which has the best metric among all codewords in S that differ from D at position j. A non-simplified Chase decoder considers every unique codeword found to be a competing codeword and updates the metric value Mj at position j accordingly.
As mentioned previously, in some situations the Chase decoder may be unable to calculate the soft output because there is no competing codeword Cj in S which differs from D at position j. FIG. 3 provides an exemplary flowchart 300 depicting processing the codewords in S.
With reference to FIG. 3, Mj represents the best competing metric at position j, where j ranges from 1 to n. The index q ranges over the number of codewords in set S. Without loss of generality, the set S is arranged so that the first codeword (q=1) in S is assumed to the best codeword D. Starting with the first position (j=1) in a codeword (block 305), metric Mj is initialized and q refers to the second codeword Cq in S (block 310). If Cq is a competing codeword at position j (block 315), then metric Mj is updated (block 320) and q is incremented (block 325). In certain embodiments if the number of codewords in set S is 0 or 1, the loop beginning before block 315 should not get executed. Otherwise, if Cq is not a competing codeword, then q is incremented (block 325).
The process of checking the codewords in the set S and updating metric Mj at position j as needed is repeated for each codeword in S (blocks 315-330). When all codewords in S have been checked at bit position j (No in block 330), the jth soft output value is computed (block 335) and the bit position index is incremented (block 340). The codeword evaluation is then repeated for the next bit position (blocks 310-335) until index j exceeds the codeword length n (block 345). In block 335, computing the j-th soft (output) value can use metric Mj.
FIG. 4 illustrates a method 400 for estimating soft output values within a product code. First the process performs all constituent SISO decodings (for example, with a Chase decoder) in one dimension of a product code (block 405). The soft outputs can contain a combination of non-estimated (valid) soft output values and invalid soft output values. A valid soft output value is produced if the SISO decoder is able to find a competing codeword for that bit position. An invalid soft output value occurs if the SISO decoder is unable to find a competing codeword for that bit position. Next, the process finds all the valid soft output values within the product code (block 410). Next, the valid soft output values are processed. One processing method involves computing the valid extrinsic values from the valid soft output values and corresponding soft input values (block 415). Next, the mean of the magnitudes of the valid extrinsic values is computed. Next, an estimated extrinsic value is computed based on scaling and normalizing the mean (block 420). The scaling operation can simply be a multiplication by a constant. The normalizing operation often involves a division by a value that can be variable and dependent on the received vector for example. The last operation replaces the invalid soft output values with estimated soft output values that are based on the estimated extrinsic value (block 425).
The normalization operation can cause the product code decoder to be scale intolerant. A scale-intolerant operation is non-homogenous, i.e., if f(x)=y, then f(ax)≢ay. In contrast, a scale-tolerant operation is homogenous, i.e., f(x)=y, then f(ax)=ay for values of a. A non-homogenous operation is also non-linear, in that if f(x1)=y1 and f(x2)=y2, then f(ax1+bx2)≢ay1+by2. For example, x can repres input (LLR), y can represent an output (LLR), and f(•) can represent a decoder. Scale-tolerant operations are desirable for many reasons. Among the reasons is scale tolerance facilitates fixed-point implementations, such as on a Motorola Model DSP56600 digital signal processor.